List of Topics

Обозначения:
$\dagger$ - требует рефактора
$\star$ - без док-ва тем, кто ходил на лекции
$\star \star$ - только формулировки всем

Темы

◦ Декартово произведение и его свойства
◦ Бинарное отношение, его матрица
◦ Операции над бинарными отношениями: дизъюнкция, конъюнкция и отрицание, обращение, композиция, возведение в степень
◦ Операции в матричном виде
◦ Мультимножества, операции над мультимножествами
◦ Мультиотношения
◦ Орграф бинарного отношения
◦ Связь между свойствами бинарного отношения и его орграфа
◦ Теорема о матрице орграфа и расстояния между вершинами в орграфе
◦ Оператор замыкания
◦ Замыкания свойств отношений
◦ Теорема о транзитивном замыкании
◦ Частичные порядки
◦ ЧУМ
◦ Сравнимость, несравнимость элементов
◦ Экстремальные элементы
◦ Отношения покрытия, диаграмма Хассе
◦ Изоморфизм ЧУМ
◦ Двойственные ЧУМ
◦ Операции над ЧУМ (объединение, сумма, произведение)
◦ Линейный порядок
◦ ЛУМ
◦ Теорема о продолжении ЧУМ до ЛУМ
◦ Условия минимальности, индуктивности, обрыва убывающих цепей
◦ $\star$ Теорема об их эквивалентности
◦ Нижние и верхние границы в ЧУМ
◦ Инфимум и супремум (их свойства)
◦ Полурешетки
◦ Решетки
◦ Тождество поглощения
◦ Определение решеток через операции
◦ Эквивалентность определений
◦ Подрешетки
◦ Законы дистрибутивности в решетках
◦ Дистрибутивные решетки
◦ Критерий дистрибутивности решетки (доказательство только в одну сторону)
◦ Дополнения в решетке
◦ Теорема о дополнении в дистрибутивной решетке
◦ Булевы алгебры
◦ $\star \star$ Теорема о булевой алгебре и булеане
◦ Равномощность множеств
◦ Мощность множества, кардинальные числа
◦ Парадокс Рассела
◦ $\star \star$ Аксиоматика ZFC, аксиома выбора
◦ Конечные, счетные множества
◦ Теорема о бесконечном множестве
◦ Сравнение мощностей
◦ Теорема Кантора-Бронштейна
◦ Вполне упорядоченное множества
◦ $\star \star$ Теорема о порядке на множестве кардинальных чисел
◦ Теорема Кантора о мощности булеана
◦ Теорема о равномощности $\mathbb{R}$ и булеана счетного множества
◦ Мощность континуума
◦ Теорема о бесконечном множества наименьшей мощности
◦ Теорема об объединений счетного или конечного числа счетных множеств
◦ Понятие о континуум-гипотезе
◦ Базовые комбинаторные понятия из ВВМ: размещения, перестановки, правило произведения (в курсе не было, но это фундамент, не надо много читать, только что это и как применяется)
◦ Биномиальные коэффициенты (их различные характеризации: через количество подмножеств, через биномиальные коэффициенты, через количество двоичных векторов, их эквивалентность)
◦ Рекуррентные соотношения (треугольник Паскаля)
◦ Свойства биномиальных коэффициентов (основная формула, симметричность, сумма четных/нечетных, сумма всех коэффициентов и пр.)
◦ Пути в целочисленной решетке
◦ Числа Каталана
◦ Теорема о числах Каталана
◦ Другие характеризации чисел Каталана (правильные расстановки скобок, полные бинарные деревья)
◦ Перестановки
◦ Граф перестановки
◦ Циклическая запись (канонический вид)
◦ Симметрическая группа
◦ Порядок элемента
◦ Циклическая подгруппа
◦ Наибольший порядок перестановки
◦ Функция Ландау
◦ $\star \star$ Асимптотика функции Ландау
◦ Числа Стирлинга 1-го рода
◦ Рекуррентная формула
◦ Восходящий факториал
◦ Теорема о связи восходящих факториалов и степенных функций
◦ $\star$ Перестановки с двумя циклами
◦ $\star$ Гармонические числа
◦ Теорема Кэли
◦ $\star$ Транспозиции
◦ $\star$ Умножение перестановки на транспозицию слева и справа (объяснить, что и как переставляется)
◦ $\star$ Порождающее множество группы
◦ $\star$ Теорема о том, что $S_n$ порождается своими транспозициями
◦ $\star$ Действие перестановки на множестве
◦ $\star$ BWT
◦ Принцип включения-исключения
◦ Теорема о ПВИ
◦ Симметричный случай ПВИ
◦ Число сюръекций
◦ Числа Стирлинга 2-го рода
◦ Рекуррентная формула для чисел Стирлинга 2-го рода
◦ Число Белла
◦ Число разбиений на классы эквивалентности
◦ $\star$ Функция Эйлера для количества меньших взаимно простых чисел
◦ $\star$ Теорема о формуле функции Эйлера
◦ Беспорядки
◦ Теорема о количестве беспорядков
◦ Рекуррентные соотношения
◦ Линейные рекуррентные соотношения
◦ Теорема о линейных рекуррентных соотношений 1-го порядка.
◦ Линейные рекуррентные соотношения с постоянными коэффициентами
◦ Частные и общее решения
◦ Теорема о размерности пространства решений ЛОРСПК
◦ Характеристические многочлены ЛОРСПК
◦ Теорема о решении ЛОРСПК и корнях характеристического уравнения
◦ Теорема о ЛНЗ решении ЛОРСПК в случае различных корней
◦ Теорема об решений в случае простых корней
◦ Теорема о решениях ЛОРСПК соответствующих кратному корню
◦ Леммы к теореме об общем решении
◦ $\star$ Теорема о виде общего решения
◦ Определение различных O-символик (4 типа)
◦ Простейшие свойства
◦ Формула Стирлинга и ее уточнение
◦ $\star$ Асимптотика n-го простого числа
◦ Понятие графа (орграфа)
◦ Петли, кратные ребра
◦ Мультиграфы
◦ Матрица смежности графа
◦ Степени вершин
◦ Обыкновенные графы
◦ Маршруты, цепи, пути, циклы
◦ Длина маршрута
◦ Достижимость вершин
◦ Связность графа, компоненты связности
◦ Лемма о простой цепи
◦ Подграфы
◦ Суграфы
◦ Порожденные подграфы
◦ Операции удаления ребра и удаление вершины
◦ Лемма об удалении ребра и связности
◦ Изоморфизм графов
◦ Матрица перестановки
◦ Изоморфизм графов и матрица перестановки
◦ Двудольные графы
◦ Задача назначениях, задача о свадьбах
◦ Критерий двудольности графа
◦ Эйлеровы графы
◦ Эйлеровы циклы и эйлеровы пути
◦ Полуэйлеровы графы
◦ Критерий эйлеровости графа
◦ Алгоритм Флери
◦ Критерий полуэйлерости графа
◦ Критерий эйлеровости орграфа
◦ Задача китайского почтальона: в взвешенном графе найти реберный маршрут минимального веса
◦ Мосты и точки сочленения
◦ Лемма о мосте
◦ Лемма о точке сочленения
◦ Двусвязные графы
◦ Блоки
◦ Лемма о пересечении двух блоков
◦ Дерево блоков и точек сочленения (с доказательством корректности)
◦ Гамильтоновы цикл
◦ Гамильтоновы пути
◦ Гамильтоновы граф
◦ Задача коммивояжера (TSP)
◦ Вариант со взвешенным графом
◦ Евклидова TSP
◦ Метрическая TSP
◦ Теорема Оре о гамильтонов графе
◦ Теорема о 2-связности гамильтонова графа
◦ $\star$ Обобщенная точкой сочленения $k$-го порядка
◦ $\star$ Теорема о негамильтоновости и обобщенной точке сочленения $VC$
◦ Изображение графа
◦ Правильное (плоское) изображение
◦ Плоские графы
◦ Планарные графы
◦ Укладывается графа на сфере и планарность
◦ Грани плоского графа и границы граней
◦ Внешняя грань
◦ Лемма о числе граней для ребра
◦ Следствие о суммарной длине всех границ граней
◦ Теорема Эйлера для связного плоского графа
◦ [[theorems/Следствие о числе ребер планарного графа|Непланарность K_5 и K_3,
3.]]
◦ Операция стягивания ребра
◦ Миноры графа
◦ Теорема Вагнера (док-во только в одну сторону).
◦ Независимое множество вершин в графе
◦ Типы задач связанных с независимыми множествами
◦ Раскраски графов
◦ Правильные раскраски
◦ k-раскрашиваемые графы
◦ Хроматическое число графа
◦ Лемма о нижних оценках хроматического числа (через кликовое число и число независимости)
◦ Теорема о связи хроматического число графа и хроматического числа его блоков
◦ Лемма о жадной оценке (хроматическое число и максимальная степень вершины)
◦ $\star \star$ Теорема Брукса (только формулировка)
◦ Задача раскраски плоского графа
◦ Теорема о четырех красках
◦ Лемма о вершине степени <= 5
◦ Теорема Хивуда о 5 цветах
◦ Алфавит
◦ Детерминированные конечные автоматы
◦ Недетерминированные конечные автоматы
◦ Теорема Рабина-Скотта
◦ Алгоритм построения ДКА по НКА
◦ Слово
◦ Длина слова
◦ Конкатенация слов
◦ Языки
◦ Теоретико-множественные операции над языками
◦ Умножение языков, итерация
◦ Свойства операций
◦ Элементарные регулярные языки
◦ Регулярные языки
◦ Теорема Клини о регулярных языках
◦ Логические переменные
◦ Булевы функции
◦ Таблицы истинности
◦ Фиктивные переменные
◦ Композиция булевых функций
◦ Основные булевы операции, их свойства
◦ Литералы
◦ Элементарные конъюнкции
◦ ДНФ и СДНФ
◦ Теорема о СДНФ
◦ Следствие о ДНФ
◦ Карты Карно
◦ Элементарные дизъюнкции (клозы). КНФ и СКНФ
◦ Теорема о СКНФ. Следствие о КНФ
◦ Полные системы булевых функций
◦ Полиномы Жегалкина. Свойства операции "+"
◦ Теорема о полноте полиномов Жегалкина
◦ Замкнутые классы
◦ Основные пять замкнутых классов. Леммы о замкнутости этих классов
◦ Лемма о несамодвойственной функции
◦ Лемма о немонотонной функции
◦ Лемма о нелинейной функции
◦ Теорема Поста
◦ Базисы класса булевых функций
◦ Атомы и коатомы решетки
◦ Теорема о том, что 5 классов — коатомы
◦ Логическое следствие
◦ Правило резолюций
◦ Теорема о полноте метода резолюций
◦ Задача SAT
◦ Метод распространения переменной
◦ Хорновская выполнимость
◦ 2-SAT